package sort;
/**
 * 希尔排序 O(n^1.3-1.5)
 * 缩小增量排序：
 *    先选定一个整数gap,（gap一般选为数组长度的一半，或1/3）。
 *    将待排序的数组按gap分组，不同组之间内部使用插入排序法。
 *    此时数组有序性得到了加强，再将gap/=2 或 gap/=3, 重复此流程，直到gap = 1。
 *    最后再进行一次插入排序。
 */
public class ShellSort {
    //希尔排序
    public static void shellSort(int[] arr){
        int gap = arr.length / 2;
        //预处理阶段
        while(gap > 1){
            insertionByGap(arr, gap);
            gap /= 2;
        }
        //最后一次全集合排序
        InsertionSort.insertionSort(arr);
    }

    //按gap分组进行插入排序
    private static void insertionByGap(int[] arr, int gap) {
        //9 1 2 5 7 4 8 6 3 5
        //gap之前的元素都是每组的第一个元素，所以不处理
        //而且分组处理并不是先处理完一组的元素，再去处理下一组元素；而是挨个儿遍历每个元素，判断它的组别去处理
        for(int i = gap; i < arr.length; i++){
            //从该组的待处理元素开始，向前比较该组处理过的最后一个元素，判断是否需要交换
            for(int j = i; j-gap >= 0 && arr[j] < arr[j-gap]; j -= gap){
                swap(arr, j, j - gap);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] + arr[j] - (arr[j] = arr[i]);
    }
}
